class Solution:
    def sortString(self, s: str) -> str:
        bucket = {}
        sortArray = []
        res = ""
        for c in s:
            if(c not in bucket):
                sortArray.append(c)
                bucket[c] = 1
            else:
                bucket[c] += 1
        sortArray.sort()
        realIndex = 0
        for i in range(0, len(sortArray)):
            ch = sortArray[realIndex]
            res += ch
            if(bucket[ch] == 1):
                sortArray.pop(realIndex)
                del bucket[ch]
            else:
                bucket[ch] -= 1
                realIndex += 1
        realIndex = len(sortArray)-1
        for i in range(len(sortArray)-1, -1, -1):
            ch = sortArray[i]
            res += ch
            if(bucket[ch] == 1):
                sortArray.pop(realIndex)
                del bucket[ch]
            else:
                bucket[ch] -= 1
                realIndex -= 1
        return res


if __name__ == "__main__":
    print(Solution().sortString("leetcode"))
    print(Solution().sortString("rat"))
    print(Solution().sortString("spo"))
    pass
